import java.util.*;

public class Solution {
    // 题目1：数组中的第K个最大元素
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        for(int parent = (n - 1 - 1) / 2; parent >= 0; parent--){
            buildPriorityQueue(nums, parent, n);
        }

        for(int i = n - 1; i > n - k ; i--){
            swap(nums, 0, i);
            buildPriorityQueue(nums, 0, i);
        }

        return nums[0];


    }

    private void buildPriorityQueue(int[] arr, int parent, int len){
        int child = 2 * parent + 1;
        while(child < len){
            if(child + 1 < len && arr[child] < arr[child + 1]){
                child++;
            }

            if(arr[child] > arr[parent]){
                swap(arr, child, parent);

                parent = child;
                child = 2 * parent + 1;
            }else{
                break;
            }
        }
    }

    private void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 题目2：最小 k 个数
    class Cmp implements Comparator<Integer>{
        @Override
        public int compare(Integer a, Integer b){
            return b - a;
        }
    }
    public int[] smallestK(int[] arr, int k) {
        int[] nums = new int[k];
        if(k == 0 || arr.length == 0){
            return nums;
        }
        Cmp cmp = new Cmp();
        Queue<Integer> q = new PriorityQueue<>(cmp);
        for(int i = 0; i < k; i++){
            q.offer(arr[i]);
        }

        for(int i = k; i < arr.length; i++){
            if(arr[i] < q.peek()){
                q.poll();
                q.offer(arr[i]);
            }
        }

        for(int i = 0; i < k; i++){
            nums[i] = q.poll();
        }

        return nums;
    }

    // 题目3：第三大的数
    // 1 <= nums.length <= 104
    //-2^31 <= nums[i] <= 2^31 - 1
    // 选择 Long.MIN_VALUE 而不是 Integer.MIN_VALUE
    // 因为 Integer.MIN_VALUE 这个值在数组的取值范围内，而这个起的作用类似于 flag ， 不应该跟数组中的值相等。

    long a = Long.MIN_VALUE;
    long b = Long.MIN_VALUE;
    long c = Long.MIN_VALUE;
    public int thirdMax(int[] nums) {
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > a){
                c = b;
                b = a;
                a = nums[i];
            }else if(nums[i] > b && a > nums[i]){
                c = b;
                b = nums[i];
            }else if(nums[i] > c && b > nums[i]){
                c = nums[i];
            }
        }

        return (int)(c == Long.MIN_VALUE ? a : c) ;
    }

    // 题目4：最接近原点的 K 个点
    class Cmp1 implements Comparator<int[]>{
        @Override
        public int compare(int[] a, int[] b){
            return b[0] - a[0];
        }
    }

    public int[][] kClosest(int[][] points, int k) {
        int[][] ans = new int[k][2];
        Cmp1 cmp = new Cmp1();
        Queue<int[]> q = new PriorityQueue<>(cmp);
        for(int i = 0; i < k; i++){
            q.offer(new int[]{points[i][0] * points[i][0] + points[i][1] * points[i][1], i});
        }

        for(int i = k ; i < points.length; i++){
            int temp = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            if(q.peek()[0] > temp){
                q.poll();
                q.offer(new int[]{temp, i});
            }
        }

        for(int i = 0; i < k; i++){
            ans[i] = points[q.poll()[1]];
        }

        return ans;
    }

    // 题目5：前 K 个高频元素
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int x : nums){
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        Queue<Integer> q = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer a, Integer b){
                return map.get(a) - map.get(b);
            }
        });
        for(Integer key : map.keySet()){
            if(q.size() < k){
                q.offer(key);
            }else if(map.get(key) > map.get(q.peek())){
                q.poll();
                q.offer(key);
            }
        }
        int[] ans = new int[k];
        for(int i = 0; i < k; i++){
            ans[i] = q.poll();
        }
        return ans;
    }

    // 题目6：根据字符出现频率排序
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();

        for(Character c : s.toCharArray()){
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        List<Character> list = new LinkedList<>(map.keySet());

        Collections.sort(list, new Comparator<Character>(){
            @Override
            public int compare(Character a, Character b){
                return map.get(b) - map.get(a);
            }
        });

        StringBuilder stringBuilder = new StringBuilder();
        for(int i = 0; i < list.size(); i++){
            char c = list.get(i);
            int freg = map.get(c);
            for(int j = 0; j < freg; j++){
                stringBuilder.append(c);
            }
        }
        return stringBuilder.toString();
    }

    // 题目7：数组中两元素的最大乘积
    // 使用各大排序做一次吧~~
    // Ⅰ. 插入排序
    // ①直接插入排序
    public int maxProduct(int[] nums) {
        for(int i = 1; i < nums.length; i++){
            int j  = i - 1;
            int temp = nums[i];
            for(; j >= 0; j--){
                if(nums[j] < temp){
                    nums[j + 1] = nums[j];
                }else{
                    break;
                }
            }
            nums[j + 1] = temp;
        }
        return (nums[0] - 1) * (nums[1] - 1);
    }

    // ②希尔排序
    public int maxProduct1(int[] nums) {
        int gap = nums.length;
        while(gap >= 1){
            gap /= 2;
            shellSort(nums, gap);
        }
        return (nums[0] - 1) * (nums[1] - 1);
    }

    private void shellSort(int[] nums, int gap){
        for(int i = gap; i < nums.length; i++){
            int j = i - gap;
            int temp = nums[i];
            for(; j >= 0; j -= gap){
                if(nums[j] < temp){
                    nums[j + gap] = nums[j];
                }else{
                    break;
                }
            }
            nums[j + gap] = temp;
        }
    }

    // 选择排序
    public int maxProduct2(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int minIndex = left;
            int maxIndex = left;
            for(int i = left + 1; i <= right; i++){
                if(nums[i] > nums[maxIndex]){
                    maxIndex = i;
                }
                if(nums[i] < nums[minIndex]){
                    minIndex = i;
                }
            }
            swap(nums, left, maxIndex);
            if(minIndex == left){
                minIndex = maxIndex;
            }
            swap(nums, right, minIndex);
            left++;
            right--;
        }

        return (nums[0] - 1) * (nums[1] - 1);
    }

    // 还可以这样子做：
    int a1 = Integer.MIN_VALUE;
    int b1 = Integer.MIN_VALUE;
    public int maxProduct3(int[] nums) {
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > a1){
                b1 = a1;
                a1 = nums[i];
            }else if(a1 >= nums[i] &&nums[i] > b1  ){
                b1 = nums[i];
            }
        }
        return (a1 - 1) * (b1 - 1);
    }

    // 题目8： 装满杯子需要的最短总时长
    public int fillCups(int[] amount) {
        int sum = 0;
        int max = 0;
        for(int i = 0; i < amount.length; i++){
            sum += amount[i];
            max = Math.max(amount[i], max);
        }

        if(amount[0] == 0 || amount[1] == 0 || amount[2] == 0|| amount[0] + amount[1] <= max || amount[1] + amount[2] <= max || amount[0] + amount[2] <= max){
            return max;
        }
        return sum % 2 == 1 ? sum / 2 + 1 : sum / 2;
    }

    // 假设不同类型杯子的数量分别为 x, y 和 z，其中 x≤y≤zx
    //
    //如果 x+y≤z，那么每次装满 z 的时候，可以同时装满 x 或 y，因此总时长为 z。
    //
    //如果 x+y>z，最少的秒数，对于偶数来说，是 (x + y + z) / 2
    // 对于奇数来说，(x + y + z) / 2 + 1
    // 可以合并成 (x + y + z + 1) / 2
    public int fillCups1(int[] amount) {
        int max = 0;
        int sum = 0;
        for(int i = 0; i < 3; i++){
            max = Math.max(max, amount[i]);
            sum += amount[i];
        }
        return Math.max(max, (sum + 1) / 2);
    }

    // 题目9：从数量最多的堆取走礼物
    class Cmp2 implements Comparator<Integer>{
        @Override
        public int compare(Integer a, Integer b){
            return b - a;
        }
    }
    public long pickGifts(int[] gifts, int k) {
        Cmp2 cmp = new Cmp2();
        Queue<Integer> q = new PriorityQueue<>(cmp);
        int n = gifts.length;
        for(int i = 0; i < n; i++){
            q.offer(gifts[i]);
        }
        for(int i = 0; i < k; i++){
            int num = q.poll();
            q.offer((int)Math.sqrt(num));
        }
        long sum = 0;
        for(int i = 0; i < n; i++){
            sum += q.poll();
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] arr = {1,5,72,6,87,9,29};
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
        Arrays.sort(arr, new Comparator<Integer>(){
            @Override
            public int compare(Integer a, Integer b){
                return b - a;
            }
        });
    }

}
